#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;


//refer to mit handout
//http://www2.myoops.org/course_material/mit/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/30C68118-E436-4FE3-8C79-6BAFBB07D935/0/ps9sol.pdf

double findMedianHelper(vector<int> A, vector<int> B, int left, int right, int m, int n)
{
    if (left > right)
        return findMedianHelper(B, A, max(1, (m+n)/2 - m), min(n, (m+n)/2), n, m);

    int indexA = (left+right)/2;
    int indexB = (m+n+1)/2 - indexA;
    if ((indexB ==1 || A[indexA-1] >= B[indexB-1]) && (indexB == n || A[indexA-1] <= B[indexB])) {
        if ((m+n)&0x1 == 1)
            return A[indexA-1];
        else {
            if (indexB != n) {
                int next = min(A[indexA], B[indexB]);
                return (double)(A[indexA-1] + next)/2;
            } else {
                return(double) (A[indexA-1] + A[indexA])/2;
            }
        }
    } else if (A[indexA-1] < B[indexB-1] || indexB > n) {
        //cout << "Jump to here" << endl;
        return findMedianHelper(A, B, indexA + 1, right, m, n);
    } else {
        return findMedianHelper(A, B, left, indexA -1, m, n);
    }
}

class Solution {
    public:
        double findMedianSortedArrays(int A[], int m, int B[], int n) {
            if (m > n) return findMedianSortedArrays(B, n, A, m);
            vector<int> Avec, Bvec;
            Avec.push_back(INT_MIN);
            Bvec.push_back(INT_MIN);
            for (int i = 0; i < m; i++)
                Avec.push_back(A[i]);
            for (int i = 0; i < n; i++)
                Bvec.push_back(B[i]);
            Avec.push_back(INT_MAX);
            Bvec.push_back(INT_MAX);
            m += 2;
            n += 2;
            return findMedianHelper(Avec, Bvec, max(1, (m+n)/2-n), min(m, (m+n)/2), m, n);

        }
};

//test in 1337 online judge and pass all the test
int main(int argc, char **argv)
{
    Solution mySolution;


    cout << "-----------------Test 1--------------------" << endl;
    int A1[] = {1,3,4};
    int B1[]= {2,5,6,8,9,10};
    double result = mySolution.findMedianSortedArrays(A1, sizeof(A1)/sizeof(int), B1, sizeof(B1)/sizeof(int));
    cout << result << endl;

    cout << "-----------------Test 2--------------------" << endl;
    int A2[] = {1,3,4,7};
    int B2[]= {2,5,6,8,9,10};
    double result1 = mySolution.findMedianSortedArrays(A2, sizeof(A2)/sizeof(int), B2, sizeof(B2)/sizeof(int));
    cout << result1 << endl;

    cout << "-----------------Test 3--------------------" << endl;
    int A3[] = {1,2,3};
    int B3[]= {1,2};
    double result3 = mySolution.findMedianSortedArrays(A3, sizeof(A3)/sizeof(int), B3, sizeof(B3)/sizeof(int));
    cout << result3 << endl;

    cout << "-----------------Test 4--------------------" << endl;
    int A4[] = {};
    int B4[]= {2,5,6,8,9,10};
    double result4 = mySolution.findMedianSortedArrays(A4, sizeof(A4)/sizeof(int), B4, sizeof(B4)/sizeof(int));
    cout << result4 << endl;


    cout << "-----------------Test 5--------------------" << endl;

}
